#include <unordered_map>

using namespace std;


struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


/**
 * 437. 路径总和 III
 * https://leetcode.cn/problems/path-sum-iii/
 */
class Solution {
private:
    unordered_map<long long, int> prefix;  // 前缀和
public:
    // O(n) O(n)
    // 定义节点的前缀和为：由根结点到当前结点的路径上所有节点的和。
    // 假设当前从 root 到节点 node 的前缀和为 curr：
    // + 假设从 root 到节点 node 的路径上存在节点 p_i 到 root 的前缀和为 curr-targetSum
    // + 则节点 p_i+1 到节点 node 的路径上的和为 targetSum
    int pathSum(TreeNode* root, int targetSum) {
        prefix[0] = 1;
        return dfs(root, 0, targetSum);
    }

    int dfs(TreeNode* root, long long curr, int targetSum) {
        if (!root) return 0;

        int ret = 0;
        curr += root->val;
        if (prefix.count(curr-targetSum)) {
            ret = prefix[curr-targetSum];
        }

        prefix[curr]++;
        ret += dfs(root->left, curr, targetSum);
        ret += dfs(root->right, curr, targetSum);
        prefix[curr]--;

        return ret;
    }
};
